1. Field of the Invention
The present invention relates to a broadcast encryption method. More particularly, the present invention relates to a method of managing a user key for a broadcast encryption.
2. Description of Related Art
A broadcast encryption (BE) refers to a method for effectively transferring information to the requesting users among all users by a transmitter (i.e., a broadcast center), and should effectively be used in cases where the users, who will receive the information, are voluntarily and dynamically changed. One of the most important properties of the BE is the revocation or expiration of unwanted users (for example, revoked users or users whose use term has expired).
FIG. 1 is a view illustrating the network structure of a data transmission system according to a general broadcast encryption. Referring to FIG. 1, a contents producer 100 produces various kinds of useful data including audio/video data, and provides the produced data to a service provider 110. The service provider 110 broadcasts the data provided from the contents producer 100 to authorized users (for example, a digital right management (DRM) network 140 and a smart home DRM network 150) who have paid for the corresponding data through various kinds of wire/wireless communication networks.
Specifically, the service provider 110 may transmit the data to user devices such as a set-top box 141, which is provided with various kinds of satellite receivers, through a satellite 120, or may transmit the data to a mobile communication terminal 142 through a mobile communication network (Mobile DRM). Additionally, the service provider 110 may transmit the data to various kinds of terminals 151, 152, 153, 154 and 155 of the smart home network DRM 150 through Internet 130.
Meanwhile, in order to prevent a revoked user 160 from using the data for which he or she has not paid, the data is encrypted by the broadcast encryption (BE).
The security in an encryption/decryption system mostly depends upon a system that manages encryption keys. One of the most important items in such an encryption/decryption system is how an encryption key is derived. It is also important to manage and update the derived encryption key.
The BE has greatly been changed since its concept was originally proposed, in 1991. The current BE assumes a stateless receiver. This means that secret keys of respective users are not changed or updated at all according to the change of session. In this case, a term ‘k-resilient’ is used for security, and means that information cannot be resilient even if k users among revoked users deliver a traitor attack. Since ‘r’ indicates the number of revoked users, the term ‘r-resilient’ means that the information is secured even if all the revoked users deliver the traitor attack.
Meanwhile, in the BE, a transmission overhead (i.e., overhead in transmitting a header by a transmitter side), a storage overhead (i.e., overhead is storing a secret key by the user), and a computation overhead (i.e., overhead in obtaining a session key for the user) are regarded as important, and mean. Among them, the reduction of the transmission overhead is an important problem to be solved. The transmission overhead was in proportion to the total number of users N at an initial stage, but at present, it is reduced so that it is mainly in proportion to the number r of revoked users. As schemes for making the transmission overhead in proportion to the number r of revoked users are appearing, the reduction of the transmission overhead less than r becomes an important problem to be solved in the BE.
Among the results published up to now based on the BE problem, as described above, “Subset Difference (SD) Method” published by Naor-Naor-Lotspiech shows one of the better results. In the SD method, if the total number of users is n, a storage overhead of 0(log1+e n) and a transmission overhead of 0(2r−1) are required.
However, the SD method has a problem in efficiency in the case in which plural users use the method.
As described above, diverse algorithms have been proposed since a treatise on the BE was first published by Berkovits in 1991. Among them, important algorithms of a secret sharing type, a subset cover-free system model type, a type using a tree structure have been proposed.
First, a model based on the secret sharing will briefly be explained. The secret sharing mode was first proposed by S. Berkovits in 1991, and an efficient improvement thereof was described in a treatise entitled “Efficient Trace and Revoke Schemes” announced by ‘M. Noar’ and ‘B. Pinkas’ in 2000. In “How to Broadcast a Secret” announced by S. Berkovits, a method using a polynomial interpolation and a method using a vector based secret sharing were proposed.
According to the polynomial interpolation, the center (i.e., a broadcast center or transmitter) transmits a point (xi, yi) to the respective users through secret channels. At this time, xi is a value different from each other, and (xi, yi) is the secret key of the respective user. Then, the center selects a polynomial having a random integer j and a degree of t+j+1 in order to broadcast secret information S to t authorized users of the respective session. The polynomial P is not a secret key (xi, yi) of the t users or of any other user, but passes certain j points (x, y) and (0, S). Also, the center transmits other points different from the t+j points on the polynomial P. Accordingly, the t fair users know one point (i.e., the user's own secret key) in addition to the t+j points, and thus they can restore the polynomial P and obtain the secret information S. However, the revoked users cannot restore the polynomial P.
This method requires the transmission overhead of 0(t+j+1), storage overhead of 0(1), and computational overhead of t3 times multiplications. Additionally, this method has the advantages of easy revocation, prevention against a traitor attack, and possible traitor tracing. However, it is inefficient with respect to a large number of users and its repeated use may destroy its security, so that it experiences problems in the application.
“Effective Trace and Revoke Schemes” announced by M. Noar and B. Pinkas describes a threshold secret sharing system using Lagrange's interpolation formula. According to the Noar-Pinkas method, an r-degree polynomial can be restored if r+1 points on the polynomial are known. However, it is not impossible to restore the polynomial using r points on the polynomial. Specifically, the center selects a certain t-degree polynomial P, and provides different points on the polynomial to the users as the secret key. If r users are revoked, the center broadcast information about t points in total by adding the secret keys of r revoked users and voluntarily selected t-r points. As a result, the revoked users still know only t points even if the secret information of the revoked users is added. However, the authorized users know t+1 points, and thus the user can restore the polynomial P. Then, using this polynomial, the value of the session key P(0) is obtained.
This method also has the advantages of easy revocation, prevention against a traitor attack, and possible traitor tracing. Particularly, it has the advantage in that new users can be added, and is considerably efficient in transmission overhead (e.g., 0(t)) and storage overhead (e.g., 0(1)). However, this method has the problem in that it is impossible to revoke the users the number of which is larger than t. Additionally, the computation overhead required for the computation of the number of points or the polynomial to be transmitted depends upon t, causing inefficiency in use. Additionally, with the increase of t, the computation time is greatly increased, and thus it is difficult for a large number of users to simultaneously use this method.
Second, assuming that a set of all users is S, the subset cover-free system model defines a concept of a subset cover-free system in a set having subsets of S as its elements. If such a system can be found, the BE can be performed using the system. However, the system has a drawback in that its storage overhead and transmission overhead are in the range of 0(r log n), and thus, inefficient. Additionally, a method of making a k-resilient model by extending a 1-resilient model has been introduced. Since the efficient 1-resilient strategy can be relatively easily conceived, it is considered that such an extension is significant. However, the method already proposed greatly reduces the efficiency of the system.
Third, methods using a tree structure have recently been noticed. A logical-tree-hierarchy (LTH) method was proposed by C. K. Wong, M. Gouda and G. S. Lam in 1998. According to this method, it is immoderate to revoke a large number of users in one session. Also, since secret keys of users are changed with the lapse of sessions, this method differs from the modern BE that assumes a stateless receiver. Thereafter, “Complete Subset (CS) Cover Scheme” and “Subset Difference (SD) Scheme” were proposed by D. Naor, M. Naor, and J. Lotspiech in 2001. In both methods, it is assumed that the total number of users is n and the number of revoked users is r. A center is provided with a binary tree having a height of log n, and all nodes are allocated with the corresponding secrete keys. Leaf nodes are allocated to users, one by one.
According to the CS cover method, the respective user receives secret keys, from the center, of all nodes positioned on a path between the root node and the user's own leaf node. The respective user then stores the received secret keys. Here, a subtree that does not include even a revoked user among subtrees is called a “complete subtree (CS)”. By properly selecting the CS, all the non-revoked users can be included in the subtree. At this time, if the session key is encrypted by the secret key corresponding to the root node of the used CSs and the encrypted session key is transmitted, the authorized user can restore the session key. However, the revoked user cannot restore the session key because it is not included in any used CS.
FIG. 2 is a view explaining the concept of the broadcast encryption that allocates keys to the conventional tree structure. Referring to FIG. 2, the respective users 220 who receive data through the broadcast encryption system have their own key values (for example, 32nd to 47th users), and simultaneously have the key values of the respective nodes connected to the respective users on the tree structure.
For example, 34th user has the key value of 17th node 209, the key value of 8th node 204, the key value of 4th node 202 and the key value of 2nd node 201, in addition to its own key value, i.e., the key value of the 34th node. The key value of 17th node 209 that the 34th user has is also shared with the 35th user. In a similar manner, the key value of 8th node 204 that the 34th user has is also shared with the 32nd, 33rd, and 35th users.
Meanwhile, if the 32nd to 47th users are all authorized users, data is simultaneously transmitted to all the users with the key value of the 2nd node 201 included in a header part of the data, so that the security of the data can be maintained.
However, if the user having the key of the 36th user 221 is not an authorized user, but a revoked user, it is necessary to update the key values of the node related to the 36th user 221 since the corresponding key values are shared with other users. That is, the key values of the 18th node 210, 9th node 205, 4th node 202 and 2nd node 201 should be updated. This update of the key value is performed from a lower node to an upper node.
First, since the key value of the 18th node 210 is shared with the 37th user, the updated key value of the 18th node 210 is encrypted by the key value of the 37th user, and then the encrypted key value is transmitted from the server to the 37th user. Then, since the key value of the 9th node 205 is shared with the 37th user and with the 38th and 39th users positioned below the 19th node 211, the updated key value of the 9th node 205 is encrypted by the key value of the 18th node 210 which has already been updated and the encrypted key value is transmitted to the 37th user, while it is also encrypted by the key value of the 19th node 211 and the encrypted key value is transmitted to the 38th and 39th users.
In a similar manner, since the key value of the 4th node 202 is shared with the 32nd, 33rd, 34th and 35th users positioned below the 8th node 204 and with the 37th, 38th and 39th users positioned below the 9th node 205, the updated key value of the 4th node 202 is encrypted by the key value of the 8th node 204 to be transmitted to the 32nd to 35th users, while it is also encrypted by the key value of the 9th node 205 which has already been updated to be transmitted to the 37th, 38th and 39th users.
Last, since the key value of the 2nd node 201 is shared with all the users except for the 36th user 221 i.e., the 32nd to 35th and 37th to 39th users positioned below the 4th node 204 and with the 40th to 47th users positioned below the 5th node 203, the updated key value of the 2nd node 201 is encrypted by the key value of the 4th node 202 which has already been updated to be transmitted to the 32nd, 33rd, 34th, 35th, 37th, 38th, and 39th users, while it is also encrypted by the key value of the 5th node 203 to be transmitted to the 40th to 47th users. Through this key updating process, illegal (or revoked) user's access to the data can be intercepted and prevented.
The transmission overhead in the above-described method (i.e., CS model) is 0(r log (n/r)). That is, the transmission overhead is the number of CSs that only includes all of the non-revoked users, and the storage overhead is 0(log n).
Meanwhile, the subset difference (SD) method is a modification of the above-described CS model, and remarkably improves the transmission overhead by requesting the storage overhead of 0(log2 n) and the transmission overhead of 0(2r−1). The SD model considers a subtree obtained by subtracting a subtree that contains one node w included in another subtree as its root node from the corresponding subtree that contains another node v as its root node. Leaf nodes under this subtree denote the authorized users, and the lead nodes under the subtree having the node w as its root node denote the revoked users. If any revoked user is inserted among the proper number of authorized users, the SD model can cover it with one subset unlike the CS model that necessarily requires two or more subsets.
According to the SD method, the hash values from the hash value of the key allocated to the node v to the hash value of the key allocated to the node w are obtained, and the values corresponding to the obtained values are used as the session keys. The respective user has the hash values of sibling nodes to respective nodes on a path from the root node to the user's own leaf node as the user's secret keys. Accordingly, using the unidirectional property of the hash function, the session keys of the authorized users can be restored. This SD model has the transmission overhead of 0(2r−1), the storage overhead of 0(log2 n) and the computation overhead of 0(log n).
Thereafter, an LSD model that is an improvement of the SD model was proposed in 2002. According to the LSD model, the storage overhead is reduced to 0(log3/2 n) by using a layer in the respective subtree, but the transmission overhead is double the transmission overhead of the SD model.
The models using the tree structure such as the LSD, SD, and so on, among the above-described BE models, show a better efficiency. However, in the case of the methods using the tree structure, the number of subsets required for the broadcast greatly depends upon the positions of the users, and thus, it is difficult to expect further improvements. Additionally, in the case of the tree structure, maintenance and repair is rather costly. Accordingly, instead of the above-described method using the tree structure, more efficient BE schemes are required.